#coding=utf-8
from collections import deque
from collections import defaultdict


class Graph():
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

class BFSResult:
    def __init__(self):
        self.level = {}
        self.parent = {}

class DFSResult:
    def __init__(self):
        self.parent = {}

#虎胆龙威难题
def find_next_state(u:tuple,jug:tuple)->list:
    next_state = []
    if u[0] < jug [0]: # 把 X 壶灌满。
        next_state.append((jug[0],u[1]))
    if u[1] < jug [1]: # 把 Y 壶灌满。
        next_state.append((u[0],jug[1]))
    if u[0] > 0: # 把 X 壶倒空。
        next_state.append((0, u[1]))
    if u[1] > 0: # 把 Y 壶倒空。
        next_state.append((u[0], 0))
    if u[0] < jug[0]: # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
        if u[1] >= jug[0] - u[0]:
            next_state.append((jug[0],u[1]-(jug[0] - u[0])))
        if jug[0] - u[0] > u[1] and u[1] > 0:
            next_state.append((u[0]+u[1],0))
    if u[1] < jug[1]: # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
        if u[0] >= jug[1] - u[1]:
            next_state.append((u[0]-(jug[1] - u[1]),jug[1]))
        if jug[1] - u[1] > u[0] and u[0] > 0:
            next_state.append((0,jug[1]))
    return next_state

def bfs_diehard(start,end,jug)->bool:
    r = BFSResult()
    r.level = {start:0}
    r.parent = {start:None}
    i = 1  # 记录层编号 012
    frontier = [start]
    while frontier:
        next = []
        for u in frontier:
            for v in find_next_state(u,jug):
                if v not in r.level:
                    r.level[v] = i
                    r.parent[v] = u
                    next.append(v)
                if v == end:
                    return True
        frontier = next
        i += 1
    return False

print(bfs_diehard((0, 0), (4, 0), (5, 3)))







class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

def judge(a,b):
    if abs(a-b)<=1:
        return  True
    else:
        return  False

tree = TreeNode(3, TreeNode(9, None,None), TreeNode(20, TreeNode(15),TreeNode(7)))
tree2 = TreeNode(1, TreeNode(2, TreeNode(3,TreeNode(4),TreeNode(4)), TreeNode(3)), TreeNode(2, None, None))
a=max_depth(tree)
c = max_depth(tree2)
b=min_depth(tree)
d = min_depth(tree2)
print(judge(a,b))
print(judge(c,d))